Interval DP
Dynamic programming with the interval $ [l, r) as the domain of definition
https://gyazo.com/c26ccf2850d1bbdee5d71cea1c3bc249
There are several patterns in how to ask for it (sometimes in combination).
Find f(l, r) from f(l + 1, r) and f(l, r - 1)
Find f(l, r) from f(l, i) and f(i, r) (l < i < r)
O(N^3).
When you can't make it in time
Speed up range summation with phenic trees, etc.
3: Number of times to remove columns that satisfy the condition from the column
Figure from [PAST5L
We can remove a sequence of three elements that satisfy the condition
I want to maximize the number of pieces to remove.
I've done 1 and 2, and I'll do 3 in addition to that.
Pattern in which the remaining circles satisfy the condition after the section represented by the line is removed
---
This page is auto-translated from /nishio/区間DP using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.